class Solution {
    public:
        int minimumTotal(vector<vector<int>>& triangle) {
            for (int i = 1; i < triangle.size(); i++) {
                int j = triangle[i].size() - 1;
                triangle[i][0] += triangle[i - 1][0];
                triangle[i][j] += triangle[i - 1][j - 1];
            }
            for (int i = 2; i < triangle.size(); i++) {
                for (int j = 1; j < i; j++) {
                    triangle[i][j] +=
                        min(triangle[i - 1][j], triangle[i - 1][j - 1]);
                }
            }
            int ans = triangle[triangle.size() - 1][0];
            for (int j = 0; j < triangle.size(); j++) {
                ans = min(ans, triangle[triangle.size() - 1][j]);
            }
            return ans;
        }
    };